package leetcode101.string_problem;

/**
 * @author Synhard
 * @version 1.0
 * @class Code9
 * @description 5. 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 * 示例 1：
 *
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 *
 * 输入：s = "cbbd"
 * 输出："bb"
 * 示例 3：
 *
 * 输入：s = "a"
 * 输出："a"
 * 示例 4：
 *
 * 输入：s = "ac"
 * 输出："a"
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-05-29 15:03
 */
public class Code9 {

    public static void main(String[] args) {
        String s = "aacabdkacaa";
        System.out.println(longestPalindrome(s));
    }

    public static String longestPalindrome(String s) {
        int begin = 0, end = 0;
        int length = s.length();
        boolean[][] dp = new boolean[length + 1][length + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = false;
        }
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = false;
        }
        for (int i = 1; i < dp.length; i++) {
            dp[i][i] = true;
        }
        for (int i = dp.length - 1; i > 0; i--) {
            for (int j = dp[i].length - 1; j > i; j--) {
                boolean flag = s.charAt(i - 1) == s.charAt(j - 1);
                if (i + 1 == j || i + 2 == j) {
                    dp[i][j] = flag;
                } else {
                    dp[i][j] = dp[i + 1][j - 1] && flag;
                }
                if (flag && j - i > end - begin && dp[i][j]) {
                    end = j;
                    begin = i;
                }
            }
        }
        if (begin == end) {
            return String.valueOf(s.charAt(0));
        }
        return s.substring(begin - 1, end);
    }
}
/*
动态规划
应该从右下角开始依次向上填，每一次是从左往右填
 */